0731. 我的日程安排表 II【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 双重列表

1. 📝 题目描述

• leetcode

实现一个程序来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。

当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生 三重预订。

事件能够用一对整数 startTime 和 endTime 表示，在一个半开区间的时间 [startTime, endTime) 上预定。实数 x 的范围为 startTime <= x < endTime。

实现 MyCalendarTwo 类：

• MyCalendarTwo() 初始化日历对象。
• boolean book(int startTime, int endTime) 如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。

---

示例 1：

输入：
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
输出：
[null, true, true, true, false, true, true]

解释：
MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
myCalendarTwo.book(10, 20); // 返回 True，能够预定该日程。
myCalendarTwo.book(50, 60); // 返回 True，能够预定该日程。
myCalendarTwo.book(10, 40); // 返回 True，该日程能够被重复预定。
myCalendarTwo.book(5, 15);  // 返回 False，该日程导致了三重预定，所以不能预定。
myCalendarTwo.book(5, 10); // 返回 True，能够预定该日程，因为它不使用已经双重预订的时间 10。
myCalendarTwo.book(25, 55); // 返回 True，能够预定该日程，因为时间段 [25, 40) 将被第三个日程重复预定，时间段 [40, 50) 将被单独预定，而时间段 [50, 55) 将被第二个日程重复预定。

---

提示：

• 0 <= start < end <= 10^9
• 最多调用 book 1000 次。

2. 🎯 s.1 - 双重列表

c

typedef struct {
    int events[1000][2];
    int overlaps[1000][2];
    int eSize;
    int oSize;
} MyCalendarTwo;

MyCalendarTwo* myCalendarTwoCreate() {
    MyCalendarTwo* obj = (MyCalendarTwo*)calloc(1, sizeof(MyCalendarTwo));
    return obj;
}

bool myCalendarTwoBook(MyCalendarTwo* obj, int start, int end) {
    for (int i = 0; i < obj->oSize; i++) {
        if (start < obj->overlaps[i][1] && end > obj->overlaps[i][0]) return false;
    }
    for (int i = 0; i < obj->eSize; i++) {
        if (start < obj->events[i][1] && end > obj->events[i][0]) {
            int os = start > obj->events[i][0] ? start : obj->events[i][0];
            int oe = end < obj->events[i][1] ? end : obj->events[i][1];
            obj->overlaps[obj->oSize][0] = os;
            obj->overlaps[obj->oSize][1] = oe;
            obj->oSize++;
        }
    }
    obj->events[obj->eSize][0] = start;
    obj->events[obj->eSize][1] = end;
    obj->eSize++;
    return true;
}

void myCalendarTwoFree(MyCalendarTwo* obj) {
    free(obj);
}

js

var MyCalendarTwo = function () {
  this.events = []
  this.overlaps = []
}

/**
 * @param {number} start
 * @param {number} end
 * @return {boolean}
 */
MyCalendarTwo.prototype.book = function (start, end) {
  for (const [s, e] of this.overlaps) {
    if (start < e && end > s) return false
  }
  for (const [s, e] of this.events) {
    if (start < e && end > s) {
      this.overlaps.push([Math.max(start, s), Math.min(end, e)])
    }
  }
  this.events.push([start, end])
  return true
}

py

class MyCalendarTwo:
    def __init__(self):
        self.events = []
        self.overlaps = []

    def book(self, start: int, end: int) -> bool:
        for s, e in self.overlaps:
            if start < e and end > s:
                return False
        for s, e in self.events:
            if start < e and end > s:
                self.overlaps.append((max(start, s), min(end, e)))
        self.events.append((start, end))
        return True

• 时间复杂度：book $O(n)$，其中 n 是已预订事件数
• 空间复杂度：$O(n)$

算法思路：

• 维护两个列表：events（所有事件）和 overlaps（两次重叠的区间）
• 新事件若与 overlaps 中任一区间重叠，则会产生三重预订，拒绝
• 否则将新事件与 events 中重叠的部分加入 overlaps，再将新事件加入 events